The avoidance of error is of major interest in any data-handling system. Among the major causes of error are component failure and intermittent data signal deviation resulting from noise. Errors of the first type may be reduced in frequency by improved circuit design, by using duplicate or redundant circuits, etc. Random errors due to noise usually occur with greater frequency, and they occur with greater frequency in some parts of a digital system than in others. Errors are particularly likely where transmission of data from one system or subsystem to another is involved. The longer and noisier the transmission path, the greater the likelihood of error. Errors may also occur in computer memories where information is generally read out in the form of low-level pulses.
If it can be determined that data received from a transmission line or sampled from a memory is erroneous, it is possible to take corrective action, such as a retransmission or a resampling of the data. To this end, numerous techniques have been devised to reduce the probability of an error going undetected. The simplest and most widely used approach is the parity check method. Briefly, the digital message, including a parity bit, is transmitted and then checked at the receiving end for error. An error is detected if the checked parity does not correspond to the one transmitted. The circuit that generates the parity bit at the transmitting end is called a parity generator; the circuit that checks the parity at the receiving end is called a parity checker.
The classical method of generating parity for an n-bit signal uses n-1 exclusive-OR circuits connected in a parity tree configuration; see "Introduction to SwitchingTheory and Logical Design" by F. J. Hill and G. R. Peterson, John Wiley & Sons (1974), FIG. 8.31. And the same circuit that is used for parity generation can also be used for parity checking purposes; see "Computer Logic Design" by M. M. Mano, Prentice-Hall, Inc. (1972), pages 157-159.
The prior art parity tree consisting of exclusive-OR modules is a widely used design because it is economical. Unfortunately, it operates too slowly to satisfy the ever increasing need for a faster parity circuit which is also economical. The patent to A. F. Bulfer et al, U.S. Pat. No. 3,718,904 issued Feb. 27, 1973, discloses parity circuits that achieve increased operating speed. However, the increased maximum operating speed is achieved at the expense of a higher gate count and more complicated interconnections between the gates.